package graph.最小生成树算法;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 最小生成树算法
 *    Kruskal算法
 *    1. Kruskal算法简介
 *      Kruskal实际上可以看成一种贪心算法，每次将权值最小的边加入到树中，但是此时我们需要判断
 *      如果将当前边加入到树中之后是否成环，因为树是不可以有环的，所以整个算法的难点就在于如何
 *      判断加入当前边之后，树是否成环。
 *
 *    2. Kruskal算法的具体实现
 *      首先我们有一个完全带权值的连通图，然后我们的目的就是找到该连通图的最小生成树，Kruskal算法的具体步骤如下：
 *      1. 计算出图中所有边的权值，按照权值从小到大的顺序排列
 *      2. 扫描权值从小到大的边：
 *          如果当前边添加到树中没有成环，则将边添加到树中
 *          如果当前边添加到树中成环，则放弃当前边
 *      由于最小生成树的定义，我们可以知道，如果是n个顶点的连通图，其最小生成树的边一共有n-1条，
 *      所以如果树中的边已经有n-1了，此时最小生成树已经构建好了，返回即可
 *
 *    3. 设置数据结构实现最小生成树
 *      1. 如何存储带权边的信息
 *          采用二维数组的线性结构{[x,y,weigth]......} 其中{x,y,weight}表示：x顶点到y顶点的权值为weight
 *          然后按照weight给这个数组排序(可以直接调用jdk底层封装的快速排序+lambda表达式实现)
 *
 *      2. 如何实现判断树中是否成环
 *          采用Union Find(并查集，实现起来非常简单的一种数据结构)实现判断是否成环(Union Find结构的主要作用就是判断图的成环)
 *
 *      通过上述的两种结构我们就可以完全解决Kruskal算法的简单实现
 *
 *    4. Kruskal算法的应用
 *        由于Kruskal算法的作用是生成一个完全带权连通图的最小生成树，所以常常使用Kruskal来解决一些
 *        城市之间建设造价问题或者
 *
 */
@SuppressWarnings("all")
public class Kruskal {
    /**
     * 定义并查集结构
     */
    static class UnionFind{
        int[] root; // 父节点数组
        int[] rank; // 秩数组(主要是优化并查集的，防止树的高度过高影响查询效率)
        int maxsize; // 并查集的最大容量

        public UnionFind(int maxsize) {
            this.maxsize = maxsize;
            this.root = new int[maxsize];
            this.rank = new int[maxsize];
            for (int i = 0; i < maxsize; i++) {
                root[i] = i;
                rank[i] = 0;
            }
        }

        public int find(int x) {
            if (root[x] == x) {
                return x;
            }
            return find(root[x]);
        }

        public void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX != rootY) {
                if (rank[rootX] < rank[rootY]) {
                    root[rootX] = rootY;
                }
                else if (rank[rootX] > rank[rootY]) {
                    root[rootY] = rootX;
                }
                else if (rank[rootX] == rank[rootY]) {
                    root[rootY] = rootX;
                    rank[rootX] ++;
                }
            }
        }
    }

    /**
     * 定义使用压缩数组构建图结构
     * 压缩数组的结构: {x,y,weight(x,y)} 顶点x，顶点y，顶点x，y之间的权值
     */
    static class CompressionGraph{
        int[][] compressGraph; // 压缩数组存储图结构
        int vertexCounts; // 图的顶点数量
        int curVertexCounts; // 记录当前数组中的已经存放的节点数量

        public CompressionGraph(int vertexCounts) {
            this.vertexCounts = vertexCounts;
            this.compressGraph = new int[vertexCounts][3];
            this.curVertexCounts = 0;
        }

        /**
         * 添加带权边
         * @param x
         * @param y
         * @param weight
         */
        public void addEdge(int x,int y,int weight) {
            if (compressGraph.length == vertexCounts) {
                throw new RuntimeException("顶点数已经满，无法添加");
            }
            compressGraph[curVertexCounts] = new int[] {x,y,weight};
            curVertexCounts++;
        }

        /**
         * 按照权值对CompressGraph进行从小到大排序
         * 采用匿名内部类的方式实现Comparator接口重写compare方法
         */
        public void sortByWeieght1() {
            Arrays.sort(compressGraph, new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    return o1[2] - o2[2];
                }
            });
        }

        /**
         * 采用lambda表达式实现(推荐使用这种方式，比较简洁)
         */
        public void sortByWeight2() {
            Arrays.sort(compressGraph,(a,b)->a[2] - b[2]);
        }
    }

    CompressionGraph graph;

    public Kruskal(CompressionGraph graph) {
        this.graph = graph;
    }

    /**
     * 最小生成树  采用kruskal算法实现
     * @param graph：完全连通的带权图
     */
    public  void MinCostGenerateTree() {
        this.graph.sortByWeight2();

    }

    public static void main(String[] args) {
        // 假设顶点分别为：0,1,2,3,4,5
        CompressionGraph graph = new CompressionGraph(6);  // 构建一个定点数为6的带权连完全通图
        // 构建带权连通图
        graph.addEdge(0,1,6);
        graph.addEdge(0,3,5);
        graph.addEdge(0,2,1);
        graph.addEdge(1,2,5);
        graph.addEdge(1,4,3);
        graph.addEdge(2,3,5);
        graph.addEdge(2,4,6);
        graph.addEdge(2,5,4);
        graph.addEdge(3,5,2);
        graph.addEdge(4,5,6);
        Kruskal kruskal = new Kruskal(graph);
        kruskal.MinCostGenerateTree();
    }
}























